package 牛客.链表;

import 剑指offer.ListNode;

public class BM9删除链表的倒数第n个节点 {
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here·
        if(head==null ) {
            return null;
        }
        ListNode dummyNode=new ListNode(-1);
        dummyNode.next=head;

        ListNode fast=dummyNode;
        ListNode slow=dummyNode;

        for (int i = 0; i <n; i++) {
            fast=fast.next;
        }
        while (fast.next!=null) {
            slow=slow.next;
            fast=fast.next;
        }

        slow.next=slow.next.next;
        return dummyNode.next;
    }

    public ListNode removeNthFromEnd1 (ListNode head, int n) {
        if (head==null) {
            return null;
        }
        ListNode cur=head;
        int size=0;
        while (cur!=null) {
            size++;
            cur=cur.next;
        }

        ListNode dummyNode=new ListNode(-1);
        dummyNode.next=head;
        cur=dummyNode;
        for (int i = 0; i <size-n; i++) {
            cur=cur.next;
        }
        cur.next=cur.next.next;
        return dummyNode.next;
    }
}
